package com.leetcode.studyplan.algorithm.basis;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L_15_3Sum {

    public static void main(String[] args) {
        L_15_3Sum sum = new L_15_3Sum();
        int[] nums = {-1,0,1,2,-1,-4};
//        int[] nums = {0,0,0,0};
        List<List<Integer>> res = sum.threeSum(nums);
        System.out.println(res);
    }

    /**
     * 先排序，排序完后，方便用双指针。指针从中间开始
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> res = new ArrayList<>(new ArrayList<>());
        if (nums == null || nums.length < 3) {
            return res;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                return res; // 后面的数肯定大于0
            }

            if (i > 0 && nums[i] == nums[i - 1]) { // i不是第一个元素。去重，由于前面的一样的元素已经完成遍历，此时若元素相等，则会出现同样的问题
                continue;
            }

            int target = 0 - nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {

                int tmp = nums[left] + nums[right];
                if (tmp == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    while (left < right && nums[left] == nums[left + 1]) { //去重的作用，当前面的元素已完成，则后面的元素不用再进行计算
                        left++;
                    }
                    while (right > left && nums[right] == nums[right - 1]) { //去重
                        right--;
                    }
                    left++; // 1.若存在重复的元素，则while元素结束时，刚好是最后一个重复的元素，此处进行获取下一个不重复的元素 2. 若不存在，则遍历下一个元素
                    right--;
                } else if (tmp > target) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return res;
    }

}
